package com.hy;

import java.util.Arrays;
import java.util.Random;

/**
 * Created With IntelliJ IDEA.
 * Descriptions: 归并排序
 * author: Mr.Du
 * Date: 2022/11/9
 * Time: 20:16
 */
public class MergeSort {
    
    public static void main(String[] args) {
        MergeSort mSort = new MergeSort();
        int[] nums = new int[10];
        Random r = new Random();
        // 跑五次
        for(int i = 0;i < 5;i++){
            for(int j = 0; j < nums.length;j++){
                nums[j] = r.nextInt(1000);
            }
            System.out.println("原数组: ");
            System.out.println(Arrays.toString(nums));
            mSort.merge(nums,0,nums.length-1);
            System.out.println("堆排序后的数组: ");
            System.out.println(Arrays.toString(nums));
        }
        
    }
    
    /**
     * 分治思想
     * @param nums
     * @param start
     * @param end
     */
    public void merge(int[] nums,int start,int end){
        if(start < end){
            int mid = (end - start) / 2 + start;
            merge(nums,start,mid);
            merge(nums,mid+1,end);
            mergeSort(nums,start,mid,end);
        }
    }
    
    /**
     * 相当于将两个数组排成一个有序数组，最后将这个新数组拷贝到旧数组的原来位置
     * @param nums
     * @param start
     * @param mid
     * @param end
     */
    private void mergeSort(int[] nums, int start, int mid, int end) {
        int[] arr = new int[end - start + 1];
        int left = start,right = mid+1;
        int index = 0;
        while(left <= mid && right <= end){
            if(nums[left] > nums[right]){
                arr[index++] = nums[right++];
            }else{
                arr[index++] = nums[left++];
            }
        }
        while(left <= mid){
            arr[index++] = nums[left++];
        }
        while(right <= end){
            arr[index++] = nums[right++];
        }
        /**
         * 参数说明
         * src: 源数组
         * srcPos：起始位置
         * dest: 目标数组
         * destPos: 目标数组起始位置
         * length: 源数组长度
         */
        System.arraycopy(arr,0,nums,start,arr.length);
    }
}
